#ifndef _GRAPH_ALGORITHMS_H_
#define _GRAPH_ALGORITHMS_H_

#include "Graph.h"
#include <vector>
#include <queue>
#include <stack>


enum colors {WHITE,BLACK,GREY,WILL_GREY};
class DefaultUserClass{
public:
	void beforeStep() {}

	void beforeWhiteVertex() {}

	void beforeGreyVertex(){}

	void beforeBlackVertex(){}
	void afterCurrentStep(int vertexNum = 0){}

	void afterOverallStep() {}

	void afterDFS() {}
	
};

template<class T>
void DFSStep(Graph& graph, T* userClass,
	std::stack<int>* vertexStack, std::vector<colors>* vertexColors,
	std::vector<std::vector<int> >* adjacentList, 
	std::vector<std::vector<int>::iterator>* iteratorList) {
	while (!vertexStack->empty()){
		int currentVertex = vertexStack->top();
		
		if ((*vertexColors)[currentVertex] == WHITE){
			(*adjacentList)[currentVertex] = graph.getAdjacentList(currentVertex);
			(*iteratorList)[currentVertex] = (*adjacentList)[currentVertex].begin();
			*(vertexColors->begin() + currentVertex) = GREY;
		}
		
		if ((*iteratorList)[currentVertex] == (*adjacentList)[currentVertex].end()){
			vertexStack->pop();
			userClass->afterCurrentStep(currentVertex);
			(*adjacentList)[currentVertex].clear();
			(*vertexColors)[currentVertex] = BLACK;
		}
		else{
			int processColor = *((*iteratorList)[currentVertex]);
			if ((*vertexColors)[processColor] == WHITE){
				userClass->beforeWhiteVertex();
				vertexStack->push(processColor);
			}
			else if ((*vertexColors)[processColor] == GREY){
				userClass->beforeGreyVertex();
			}
			else if ((*vertexColors)[processColor] == BLACK){
				userClass->beforeBlackVertex();
			}
			(*iteratorList)[currentVertex] ++;
		}
		
	}
	
}

template<class T>
void DFS(Graph& graph, T* userClass = new DefaultUserClass()){

	int numberOfVertexes = graph.getVertexNum();
	std::vector<colors> vertexColors(numberOfVertexes, WHITE);
	std::stack<int> vertexStack;
	std::vector<std::vector<int> > adjacentList(numberOfVertexes);
	std::vector<std::vector<int>::iterator > iteratorList(numberOfVertexes);
	
	for (int startVertex = 0; startVertex < numberOfVertexes; ++startVertex){
		if (vertexColors[startVertex] == WHITE){
			userClass->beforeStep(startVertex);
			vertexStack.push(startVertex);
			DFSStep(graph, userClass, &vertexStack, &vertexColors,
				&adjacentList,&iteratorList);
			userClass->afterOverallStep();
		}
	}
	userClass->afterDFS();
}


template<class T>
void BFSStep(Graph& graph, T* userClass,
	std::queue<int>* vertexQueue, std::vector<colors>* vertexColors){
	while (!vertexQueue->empty()){
		int currentVertex = vertexQueue->front();
		vertexQueue->pop();
		(*vertexColors)[currentVertex] = GREY;
		std::vector<int> listAdjacents = graph.getAdjacentList(currentVertex);
		for (auto processVertex: listAdjacents){
			if ((*vertexColors)[processVertex] == WHITE){
				userClass->beforeWhiteVertex(processVertex);
				vertexQueue->push(processVertex);
				(*vertexColors)[processVertex] = WILL_GREY;
			}
			else if ((*vertexColors)[processVertex] == GREY){
				userClass->beforeGreyVertex();
			}
			else if ((*vertexColors)[processVertex] == BLACK){
				userClass->beforeBlackVertex();
			}
		}
		(*vertexColors)[currentVertex] = BLACK;
	}
}

template<class T>
void BFS(Graph& graph, T* userClass){
	int numberOfVertexes = graph.getVertexNum();
	std::vector<colors> vertexColors(numberOfVertexes, WHITE);
	std::queue<int> vertexQueue;

	for (int startVertex = 0; startVertex < numberOfVertexes; ++startVertex){
		if (vertexColors[startVertex] == WHITE){
			userClass->beforeStep(startVertex);
			vertexQueue.push(startVertex);
			BFSStep(graph, userClass, &vertexQueue,&vertexColors);
			userClass->afterOverallStep();
		}
	}
	userClass->afterDFS();
}

class topologySortClass{
private:
	std::vector<int> topologySortedArray_;
public:
	
	//void beforeStep() {}

	void beforeStep(int vertex){}

	void beforeWhiteVertex(int vertex){}

	void beforeWhiteVertex() {}

	void beforeGreyVertex(){
		throw std::logic_error("Graph contains cycles");
	}

	void beforeBlackVertex(){}
	void afterCurrentStep(int vertexNum = 0){
		topologySortedArray_.push_back(vertexNum);
	}

	void afterOverallStep() {}

	void afterDFS(){
		std::reverse(topologySortedArray_.begin(), topologySortedArray_.end());
		/*std::cout << "After topology sort:" << std::endl;
		for (size_t vertexNum = 0; vertexNum < topologySortedArray_.size(); ++vertexNum){
			std::cout << topologySortedArray_[vertexNum] << " ";
		}
		std::cout << std::endl;*/
	}
	
	std::vector<int> getTopologyOrder(){
		return topologySortedArray_;
	}
};

class SimpleBFSClass{
private:
	std::vector<int> BFSOrder_;
public:

	//void beforeStep() {}

	void beforeStep(int vertex){
		BFSOrder_.push_back(vertex);
	}

	void beforeWhiteVertex(int vertex){
		BFSOrder_.push_back(vertex);
	}


	void beforeGreyVertex(){}

	void beforeBlackVertex(){}
	void afterCurrentStep(int vertexNum = 0){}

	void afterOverallStep() {}

	void afterDFS(){}

	std::vector<int> getBFSOrder(){
		return BFSOrder_;
	}
};

#endif
